//
// Description: 543. 二叉树的直径
// Created by Loading on 2022/3/27.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

int diameterOfBinaryTree(TreeNode *root) {
    int res = 0;
    // 求二叉树深度
    function<int(TreeNode *)> depth = [&](TreeNode *node) {
        if (!node) {
            return 0;
        }
        int left = depth(node->left);
        int right = depth(node->right);
        // 更新结果，左子树深度 + 右子树深度为直径
        res = max(res, left + right);
        return max(left, right) + 1;
    };

    depth(root);

    return res;
}

int main() {
    vector<int> nums{1, 2, 3, 4, 5};
    auto root = generateTreeNode(nums);
    auto res = diameterOfBinaryTree(root);
    cout << res << endl;

    return 0;
}